import numpy as np


class Element:
    """数独游戏中的每个格子"""
    def __init__(self, num: int= None):
        if num is None:
            self.data = 0
            self.possible = np.array([1, 2, 3, 4, 5, 6, 7, 8, 9])
        else:
            self.data = num
            self.possible = np.array([])

    def exclude(self, array: np.ndarray) -> bool:
        if len(self.possible) == 0:
            return False
        temp = np.setdiff1d(self.possible, array)
        if len(temp) == 0:
            return False
        else:
            self.possible = temp
            if len(temp) == 1:
                self.data = temp[0]
                self.possible = np.array([])
            return True

    def set_data(self, data:int):
        self.data = data
        self.possible=np.array([])


class ChessBoard:
    """整个棋盘以及相关的功能方法，其中构造函数的参数由load_map()函数生成，是一个数组，表明了哪些位置有哪些值，空缺的位置用0代替"""
    def __init__(self, array: np.ndarray):
        self.error = False
        self.index = 0
        self.board = []
        self.backup = None
        array = array.reshape((81))
        for item in array:
            if item == 0:
                self.board.append(Element())
            else:
                self.board.append(Element(item))

    def __equare__(self, target1: np.ndarray, target2: np.ndarray):
        """判断两个数组内的值是不是相等"""
        if len(target1) != len(target2):
            return False
        temp = np.abs(target1-target2)
        if np.sum(temp) == 0:
            return True
        else:
            return False

    def print_board(self):
        """输出当前棋盘的值情况（有多个可能的会标出）"""
        result = ""
        for i in range(0, 9):
            for j in range(0, 9):
                if self.board[i*9 +j].data == 0:
                    result = result + str(self.board[i * 9 + j].possible)
                else:
                    result = result + str(self.board[i*9 +j].data)
            result = result + "\n"
        print(result)

    def extract_row(self, row_index: int) -> np.ndarray:
        """从棋盘中提取一行数据，转换成数组（Element -> ndarray）,未确定值的位置为0"""
        result = np.zeros((9), dtype=int)
        for i in range(0, 9):
            result[i] = self.board[row_index * 9 + i].data
        return result

    def extract_col(self, col_index: int) -> np.ndarray:
        """从棋盘中提取一列数据，转换成数组（Element -> ndarray）,未确定值的位置为0"""
        result = np.zeros((9), dtype=int)
        for i in range(0, 9):
            result[i] = self.board[i * 9 + col_index].data
        return result

    def extract_quare(self, row_index: int, col_index: int):
        """从棋盘中提取一个3x3方格的数据，转换成数组（Element -> ndarray）,未确定值的位置为0"""
        result = np.zeros((9), dtype=int)
        start_row = int(row_index/3)*3
        start_col = int(col_index/3)*3
        for i in range(0, 9):
            row = start_row + int(i/3)
            col = start_col + i%3
            result[i] = self.board[row * 9 + col].data
        return result

    def extract_row_elements(self, row_index: int) -> list:
        """从棋盘中提取一行数据，list中的元素是Element"""
        result = []
        for i in range(0, 9):
            result.append(self.board[row_index * 9 + i])
        return result

    def extract_col_elements(self, col_index: int) -> list:
        """从棋盘中提取一列数据，list中的元素是Element"""
        result = []
        for i in range(0, 9):
            result.append(self.board[i * 9 + col_index])
        return result

    def extract_square_elements(self, square_index: int) -> list:
        """从棋盘中提取3x3网格数据，list中的元素是Element"""
        result = []
        start_row = square_index // 3 * 3
        start_col = square_index % 3 * 3
        for i in range(0, 9):
            row = start_row + int(i / 3)
            col = start_col + i % 3
            result.append(self.board[row * 9 + col])
        return result

    def process_row_rule(self):
        """处理每一行的方格, 确保每一行的数据不会冲突, 除去那些不可能的值"""
        flag = False
        for i in range(0, 9):
            for j in range(0, 9):
                item = self.board[i*9+j]
                if item.data == 0:
                    temp = self.extract_row(i)
                    temp_result = item.exclude(temp)
                    if temp_result is False:
                        print("推理过程出错,在第" + str(i) + "行,第" + str(j) + "列的row")
                        self.error = True
                        return
                    if item.data != 0:
                        print("第" + str(i) + "行,第" + str(j) + "列推导出了" + str(item.data) + " (row rule)")
                        flag = True
        return flag

    def process_col_rule(self):
        """处理每一列的方格, 确保每一列的数据不会冲突, 除去那些不可能的值"""
        flag = False
        for i in range(0, 9):
            for j in range(0, 9):
                item = self.board[i*9+j]
                if item.data == 0:
                    temp = self.extract_col(j)
                    temp_result = item.exclude(temp)
                    if temp_result is False:
                        print("推理过程出错,在第" + str(i) + "行,第" + str(j) + "列的col")
                        self.error = True
                        return
                    if item.data != 0:
                        print("第" + str(i) + "行,第" + str(j) + "列推导出了" + str(item.data) + " (col rule)")
                        flag = True
        return flag

    def process_square_rule(self):
        """处理每一个3x3的方格, 确保每个方格内的数据不会冲突, 除去那些不可能的值"""
        flag = False
        for i in range(0, 9):
            for j in range(0, 9):
                item = self.board[i * 9 + j]
                if item.data == 0:
                    temp = self.extract_quare(i, j)
                    temp_result = item.exclude(temp)
                    if temp_result is False:
                        print("推理过程出错,在第" + str(i) + "行,第" + str(j) + "列的square")
                        self.error = True
                        return
                    if item.data != 0:
                        print("第" + str(i) + "行,第" + str(j) + "列推导出了" + str(item.data) + " (square rule)")
                        flag = True
        return flag

    def process_row_unique_rule(self) -> bool:
        """处理每一行中某个数字的可能性只出现一次的情况"""
        for i in range(0, 9):
            counter = np.zeros((9),dtype=int)
            for j in range(0, 9):
                element = self.board[i * 9 + j]
                if element.data == 0:
                    for item in element.possible:
                        counter[item-1] = counter[item-1]+1
            index = np.where(counter == 1)
            index = np.array(index)
            for j in range(0, 9):
                element = self.board[i * 9 + j]
                if element.data == 0:
                    for item in element.possible:
                        if item-1 in index:
                            element.set_data(item)
                            print("第" + str(i) + "行,第" + str(j) + "列推导出了" + str(element.data) + " (row unique rule)")
                            return True
        return False

    def process_col_unique_rule(self) -> bool:
        """处理每一行中某个数字的可能性只出现一次的情况"""
        for i in range(0, 9):
            counter = np.zeros((9),dtype=int)
            for j in range(0, 9):
                element = self.board[j * 9 + i]
                if element.data == 0:
                    for item in element.possible:
                        counter[item-1] = counter[item-1]+1
            index = np.where(counter == 1)
            index = np.array(index)
            for j in range(0, 9):
                element = self.board[j * 9 + i]
                if element.data == 0:
                    for item in element.possible:
                        if item-1 in index:
                            element.set_data(item)
                            print("第" + str(j) + "行,第" + str(i) + "列推导出了" + str(element.data) + " (col unique rule)")
                            return True
        return False

    def process_square_unique_rule(self) -> bool:
        """处理每个3x3网格中某个数字的可能性只出现一次的情况"""
        for i in range(0, 9):
            counter = np.zeros((9),dtype=int)
            starty = i // 3 * 3
            startx = i % 3 * 3
            elements = self.extract_quare(starty, startx)
            for element in elements:
                if element.data == 0:
                    for item in element.possible:
                        counter[item-1] = counter[item-1]+1
            index = np.where(counter == 1)
            index = np.array(index)
            for j in range(0, 9):
                element = self.board[j * 9 + i]
                if element.data == 0:
                    for item in element.possible:
                        if item-1 in index:
                            element.set_data(item)
                            print("第" + str(j) + "行,第" + str(i) + "列推导出了" + str(element.data) + " (square unique rule)")
                            return True
        return False

    def find_similary_possible(self, elements: list):
        """从一个列表中找出两个可能值相同且可能值个数为2的那些可能值, 如 [3, 4]2[3, 4]578[3,6] 中找出的是[3, 4]"""
        target_possible = []
        exclude_possible = []
        for element in elements:
            if element.data == 0 and len(element.possible) == 2:
                possible = element.possible
                find = False
                for temp in target_possible:
                    if self.__equare__(temp, possible):
                        exclude_possible.append(possible)
                        find = True
                        break
                if not find:
                    target_possible.append(possible)
        return exclude_possible

    def exclude_unpossible_value(self, elements: list, exclude_possible: list) -> bool:
        """去除那些需要排除的值(由find_similary_possible()算出), 如 [4, 5][5, 6][4, 5]中去除[4, 5]就是[4, 5]6[4, 5]"""
        modify = False
        for element in elements:
            if element.data != 0:
                continue
            for exclude in exclude_possible:
                if self.__equare__(element.possible, exclude):
                    continue
                else:
                    new_possible = np.array([], dtype=int)
                    for item in element.possible:
                        if item not in exclude:
                            new_possible = np.append(new_possible, item)
                    if len(new_possible) != len(element.possible):
                        modify = True
                    if len(new_possible) == 1:
                        element.set_data(new_possible[0])
                    else:
                        element.possible = new_possible

        return modify

    def exclude_rule(self):
        """
        从每一行(列，3x3单元格)中找出两个可能值相同且可能值个数为2的空格，然后在其他位置进行排除。
        如: 其中两个空格（还不能确定其值的格子）的可能值分别为[2, 3] [2, 3], 则该行中其他单元格位置的值不可能为2或者3
        """
        modify = False
        for index in range(0, 9):

            elements = self.extract_row_elements(index)
            target_possible = self.find_similary_possible(elements)
            modify = modify or self.exclude_unpossible_value(elements, target_possible)
            if modify:
                return modify

            elements = self.extract_col_elements(index)
            target_possible = self.find_similary_possible(elements)
            modify = modify or self.exclude_unpossible_value(elements, target_possible)
            if modify:
                return modify

            elements = self.extract_square_elements(index)
            target_possible = self.find_similary_possible(elements)
            modify = modify or self.exclude_unpossible_value(elements, target_possible)
            if modify:
                return modify

        return modify

    def backup_state(self):
        """备份当前棋盘数据，以便后续产生错误时可以恢复假设之前的数据，里面有深拷贝"""
        backup = []
        for element in self.board:
            temp = Element(element.data)
            temp.possible = element.possible.copy()
            backup.append(temp)
        self.backup = backup

    def try_rule(self):
        """在所有规则都不能找出新的数字时尝试给某个位置设置一个值, 假设的对象是棋盘中可能值个数最小的位置"""
        if self.error:
            print("**********已经返回准备尝试新的可能***********")
            self.try_rebuild()
        else:
            self.backup_state()
            self.error = False
            self.index = 0
        print("已经开始假设值")
        min = 10
        element = None
        for item in self.board:
            if item.data == 0:
                if len(item.possible) < min:
                    min = len(item.possible)
                    element = item
        if element is None:
            return
        else:
            if self.index >= len(element.possible):
                self.error = True
                print("*****************推理过程出错，无法尝试新的可能*******************")
                return
            element.set_data(element.possible[self.index])
            self.index = self.index+1

    def try_rebuild(self):
        """恢复棋盘在假设前的状态"""
        self.board = self.backup
        self.error = False

    def start_game(self):
        """开始使用规则对棋盘数据进行计算，每次基本只会更新一个位置的值, 因此在外层需要控制该函数的执行次数，以便能够计算出棋盘所有位置的值"""
        temp1 = self.process_col_rule()
        temp2 = self.process_row_rule()
        temp3 = self.process_square_rule()

        if temp1 or temp2 or temp3:
            print("-----------------------")
            return

        temp = self.process_row_unique_rule()
        if temp is False:
            temp1 = self.process_col_unique_rule()
            if temp1 is False:
                temp = self.process_square_unique_rule()
                if temp is False:
                    temp1 = self.exclude_rule()
                    if temp1 is False:
                        self.try_rule()
        # self.print_board()
        print("-----------------------")

    def verify_result(self) -> bool:
        """对当前棋盘中的数据进行检测, 验证棋盘中的每一个数据是否违反了规则. 该函数用于对最终结果进行评估"""
        verify = np.ones((9), dtype=int)

        for index in range(0, 9):
            count1 = np.zeros((9), dtype=int)
            count2 = np.zeros((9), dtype=int)
            count3 = np.zeros((9), dtype=int)
            starty = index//3 * 3
            startx = index%3 * 3
            for temp in range(0, 9):
                item1 = self.board[index * 9 + temp]
                item2 = self.board[temp * 9 + index]
                item3 = self.board[(starty+ temp//3)*9 + startx + temp%3]
                if item1.data == 0 or item2.data == 0 or item3.data == 0:
                    return False
                count1[item1.data - 1] = count1[item1.data - 1] + 1
                count2[item2.data - 1] = count2[item2.data - 1] + 1
                count3[item3.data - 1] = count3[item3.data - 1] + 1
            resu1 = np.abs(count1 - verify)
            resu2 = np.abs(count2 - verify)
            resu3 = np.abs(count3 - verify)
            if np.sum(resu1) != 0 or np.sum(resu2) != 0 or np.sum(resu3) != 0:
                return False
        return True


def load_map(path: str) -> np.ndarray:
    """从文件中加载棋盘数据, 文件中每一行数据对应棋盘的每一行数据, 数据之间没有空格和tab键, 如: 003408060 是某一行数据"""
    result = np.zeros(shape=(9, 9), dtype=int)
    with open(path, "r") as f:
        col = 0
        for line in f.readlines():
            for i in range(0, 9):
                result[col, i] = int(line[i])
            col = col + 1
    return result


if __name__=="__main__":
    # 加载棋盘数据
    chess = load_map("map.txt")

    m = ChessBoard(chess) # 创建棋盘对象
    # 设定推理次数，过少则不能算出所有的值，一般20步左右即可
    for i in range(0, 20):
        m.start_game()

    # 输出预测出的棋盘数据
    m.print_board()

    # 验证数据是否违反了规则，若验证失败，则说明推理结果是错误的
    if m.verify_result():
        print("验证通过")
    else:
        print("验证失败，结果错误")


